package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月23日
*时间：上午10:46:57
*/
public class Q109 {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        if (triangle == null || triangle[0] == null) {
            return -1;
        }
        int n = triangle.length;
        int count[][] = new int[n][n];
        count[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    count[i][j] = count[i - 1][j] + triangle[i][j];
                } else if (j == i) {
                    count[i][j] = count[i - 1][j - 1] + triangle[i][j];
                } else {
                    count[i][j] = Math.min(count[i - 1][j], count[i - 1][j - 1]) + triangle[i][j];
                }
            }
        }
        int rs = Integer.MAX_VALUE;
        for (int i : count[n - 1]) {
            if (rs > i) {
                rs = i;
            }
        }
        return rs;
    }

    @Test
    public void testA() {
        int[][] triangle = { { 2 }, { 3, 4 }, { 6, 5, 7 }, { 4, 1, 8, 3 } };
        System.out.println(minimumTotal(triangle));
    }
}
